package com.vincent.algorithms.sort;

import java.util.Arrays;
import java.util.Comparator;

/**
 *
 * 堆排序  是指利用堆这种数据结构所设计的一种排序算法。堆实际是一个完全二叉树的结构，并同时满足堆的性质：
 * 即子结点总是小于（或者大于）它的父节点。
 * 算法步骤：
 *
 * 1、(从最后一个非叶子节点开始)构建堆 构建之后堆顶 即是最大元素 (此时整个堆是无序区 但可以确定堆顶是最大元素)
 * 2、不断堆顶和最后一个无序元素交换,然后调整树重新符合堆的性质，每次重复一次无序元素会减少1个
 * 3、无序区不断减少 直到整体有序
 *
 * 平均时间复杂度O(nlogn)  建堆：o(n)，每次调整o(log n) 故最好、最坏、平均情况下：o(n*logn);
 *
 * 稳定性：不稳定
 *
 *
 *
 * Created by yangwenchang on 2017/8/24.
 */
public class HeapSort implements Sort{
    @Override
    public <T> void sort(T[] array, Comparator<? super T> c) {
        buildHeap(array,c);
        System.out.println("建大顶堆后："+Arrays.asList(array));
        for (int i=array.length-1;i>0;i--){
            Sort.swap(array,0,i);
            adjustHeap(array,0,i,c);
        }

    }

    /**
     *
     * 构建大顶堆 所有的非叶子节点i 满足 arr[i]>arr[2i+1]&&arr[i]>arr[2i+2]
     * 最后一个叶子节点的计算  (arr.length-1 - 1)/2  最后一个元素下标 减1 后 除以2
     *
     * @param array
     * @param c
     * @param <T>
     */
    public <T> void buildHeap(T[] array,Comparator<? super T> c){

        for(int i=(array.length-2)/2;i>=0;i--){
            adjustHeap(array, i,array.length,c);
        }
    }

    public <T> void adjustHeap(T[] arr,int k,int length,Comparator<? super T> c){

        T temp = arr[k];
//        巧妙利用父节点与子节点下标的关系 2*i+1 使用for循环实现了 递归调整
        for (int i=2*k+1;i<length;i=2*i+1) {
//            将i指向 左右两子节点中 较大的那一个
            if (i+1<length && c.compare(arr[i], arr[i+1]) < 0){
                i++;
            }
//            如果根节点大于 两字节点种较大的那个 则不用调整了，符合要求
//            这个是基于左右两个子堆 也是大顶堆
            if(c.compare(temp, arr[i]) >= 0){
                break;
            }
//            把根节点的值 调整为 两者中大的那个
            else {
                arr[k] = arr[i];
//                ！！！重点 修改k值 指向需要继续调整的那个点
                k=i;
            }
        }
//        被调整的 arr[k] 放入最终位置
        arr[k] = temp;
    }

    public static void main(String[] args) {

        Integer[] arr = {51,23,15,58,41,9,22,110};
        System.out.println(Arrays.asList(arr));
        new HeapSort().sort(arr,(x,y)->x-y);
        System.out.println(Arrays.asList(arr));
    }
}
